#include <vector>
using std::vector;

#include <utility>
using std::swap;


class Solution
{
public:
    // 建一个小堆 
    vector<int> heap;

    void init_heap(const vector<int>& v)
    {
        heap = v;

        int sz = heap.size();
        for (int cur_pos = (sz - 1 - 1) / 2; cur_pos >= 0; --cur_pos)
        {
            int cur = heap[cur_pos];
            int sub_cur_pos = cur_pos;
            int min_child_pos = sub_cur_pos * 2 + 1;
            while (min_child_pos < sz)
            {
                if (min_child_pos + 1 < sz && heap[min_child_pos] > heap[min_child_pos + 1])
                {
                    ++min_child_pos;
                }

                if (heap[min_child_pos] >= cur)
                {
                    break;
                }
                else
                {
                    heap[sub_cur_pos] = heap[min_child_pos];
                    sub_cur_pos = min_child_pos;
                    min_child_pos = sub_cur_pos * 2 + 1;
                }
            }

            heap[sub_cur_pos] = cur;
        }
    }

    void push(int x)
    {
        heap.push_back(x);

        // 开始检查, x是否应该在这个位置
        int cur_pos = heap.size() - 1;
        int parent_pos = (cur_pos - 1) / 2;
        while (heap[parent_pos] > heap[cur_pos])
        {
            swap(heap[parent_pos], heap[cur_pos]);
            cur_pos = parent_pos;
            parent_pos = (cur_pos - 1) / 2;
        }
        // while (1)
        // {
        //     // 因为另一个节点一定大于父节点
        //     if (heap[parent_pos] > heap[cur_pos])
        //     {
        //         swap(heap[parent_pos], heap[cur_pos]);
        //         cur_pos = parent_pos;
        //         parent_pos = (cur_pos - 1) / 2;
        //     }
        //     else
        //     {
        //         break;
        //     }
        // }
    }

    void pop()
    {
        if (heap.size() == 0)
        {
            return;
        }

        int cur = heap[heap.size() - 1];
        heap.pop_back();

        // 开始检查, x是否应该在这个位置
        int cur_pos = 0;
        int min_child_pos = 2 * cur_pos + 1;
        int new_size = heap.size();
        while (min_child_pos < new_size)
        {
            if (min_child_pos + 1 < new_size && heap[min_child_pos] > heap[min_child_pos + 1])
            {
                ++min_child_pos;
            }

            if (heap[min_child_pos] > cur)
            {
                break;
            }
            else
            {
                heap[cur_pos] = heap[min_child_pos];
                cur_pos = min_child_pos;
                min_child_pos = cur_pos * 2 + 1;
            }
        }
        heap[cur_pos] = cur;
    }

    int top()
    {
        return heap[0];
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        init_heap(stock);
        vector<int> res;
        for (int i = 0; i < cnt; ++i)
        {
            res.push_back(top());
            pop();
        }

        return res;
    }
};

int main()
{
    Solution s;
    vector<int> v = { 0,1,2,2,2,1,3,6,3,1,8,2,5,3,11,4,11,12,6,2,7,19,20,16,23,6,23,4,3,25,19,15,15,17,26,30,24,31,2,26,32,6,27,21,3,6,18,46,14,13,43,19,17,50,46,40,13,2,10,43,6,5,8,23,41,21,58,10,28,22,25,63,7,40,64,50,7,57,61,43,45,64,78,50,49,15,45,10,27,66,14,68,81,48,51,33,17,35,71,31 };
    int cnt = 24;
    s.inventoryManagement(v, cnt);

    return 0;
}